package com.atguigu.search;

import java.util.Arrays;

/**
 * @author shkstart
 * @create 2021-08-16 12:04
 */
public class FibonacciSearch {
    public static int maxSize=20;
    public static void main(String[] args) {
        int arr[]={1,8,10,89,10000,1234};
        System.out.println(fibSearch(arr,89));
    }
    //创建一个斐波那契数组
    public static int[] fib(){
        int[] f = new int[maxSize];
        f[0]=1;
        f[1]=1;
        for (int i=2;i<maxSize;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
    //斐波那契算法
    public static int fibSearch(int[] arr,int key){
        int low=0;
        int height=arr.length-1;
        //中间索引
        int mid=0;
        //斐波那契的索引
        int k=0;
        int[] f=fib();
        //使得斐波那契的数值大于数组的长度
        while (height>f[k]-1){
            k++;
        }
        //根据斐波那契的值，确定数组的长度
        int[] temp = Arrays.copyOf(arr, f[k]);
        //填充多余的空位
        for (int i=height+1;i<temp.length;i++){
            temp[i]=arr[height];
        }
        //循环排除
        while (low<=height){
            mid=low+f[k-1]-1;
            if (key<temp[mid]){
                height=mid-1;
                k--;
            }else if(key>temp[mid]){
                low=mid+1;
                k-=2;
            }else {
                //中间值必须出现在斐波那契的中间
                if (mid<=height){
                    return mid;
                }else {
                    return height;
                }
            }
        }
        return -1;
    }
}
